package com.ting.test.algorithms.堆;

public class 小顶堆 {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 5, 9, 4, 1, 8, 24, 8};
        int[] result = smallHeap(arr);
        for (int param : result) {
            System.out.print(param + ",");
        }
        System.out.println();
        for (int param : arr) {
            System.out.print(param + ",");
        }
        System.out.println();
        int heapSize = arr.length;
        for (int i = 0; i < arr.length; i++) {
            System.out.print(heapPop(arr, 0, heapSize--) + ",");
        }
    }

    private static int[] smallHeap(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        for (int i = 0; i < arr.length; i++) {
            HeapInsert(arr, i);
        }

        return arr;
    }
    /**
     * 注意，由于入堆时是依次入堆的，因此：
     * 1. 当当前元素为左节点时，不需要考虑当前入堆元素的右节点（因为不存在）
     * 2. 当当前元素为右节点时，由于是小顶堆，因此，左节点一定比父节点大，也不需要考虑当前入堆元素的左节点,只需要比较当前节点（右节点）和父节点的大小即可
     * 如果当前节点比父节点小，那么当前节点一定也比左节点小
     * @param arr
     * @param index
     */
    private static void HeapInsert(int[] arr, int index) {
        //如果当前元素比父节点小，则上移
        //注意 此处利用: -1/2=0
        while (arr[index] < arr[(index - 1) / 2]) {
            mySwap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }

    }

    private static void HeapInsert2(int[] arr, int index) {
        //如果当前元素比父节点小，则上移
        while (index > 0) {
            if (arr[index] < arr[(index - 1) / 2]) {
                mySwap(arr, index, (index - 1) / 2);
            }
            index = (index - 1) / 2;
        }

    }

    private static void mySwap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }


    /**
     * @param arr
     * @return
     */
    private static int heapPop(int[] arr, int index, int heapSize) {
        if (index >= heapSize) {
            throw new RuntimeException();
        }

        int result = arr[0];
        mySwap(arr, 0, heapSize - 1);
        arr[heapSize - 1] = Integer.MAX_VALUE;

        int left = index * 2 + 1;//找到左子节点
        int small;
        while (left < heapSize) {
            if (left + 1 < heapSize - 1) {//表明有右子节点
                small = arr[left] <= arr[left + 1] ? left : left + 1;
            } else {
                small = left;//表明没有右子节点
            }
            if (arr[index] <= arr[small]) {
                break;
            }
            mySwap(arr, index, small);
            index = small;
            left = index * 2 + 1;//找到左子节点
        }
        return result;
    }
}
